The soft output Viterbi algorithm (SOVA) is a variation of the classical Viterbi algorithm. The Viterbi algorithm is a programming algorithm for finding the Viterbi path (e.g., most likely sequence of hidden states) that result in a particular sequence of events. The forward algorithm is a closely related algorithm for computing the probability of a sequence of events.
The Viterbi algorithm makes a number of assumptions. First, both the observed events and hidden events must be in a sequence. Second, these two sequences need to be aligned, and an instance of an observed event needs to correspond to exactly one instance of a hidden event. Third, computing the most likely hidden sequence up to a certain point t must depend only on the observed event at point t, and the most likely sequence at point t−1.
The terms “Viterbi path” and “Viterbi algorithm” are also applied to related dynamic programming algorithms that discover the single most likely explanation for an observed event. For example, in statistical parsing, a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is sometimes called the “Viterbi parse”.
SOVA differs from the classical Viterbi algorithm in that SOVA uses a modified path metric that takes into account the a priori probabilities of the input symbols, and produces a soft output indicating the reliability of the decision. In some implementations of SOVA, the first step is the selection of the survivor path, passing through one unique node at each time instant, t. It is known that since each node has 2 branches converging at it (with one branch being chosen to form the Survivor Path, and the other being discarded), the difference in the branch metrics (or cost) between the chosen and discarded branches indicate the amount of error in the choice. This cost is accumulated over the entire sliding window (usually equals at least five constraint lengths), to indicate the soft output measure of reliability of the hard bit decision of the Viterbi algorithm.
The traditional SOVA computes a log-likelihood ratio (LLR) as the minimum difference between the log of the probability of the path leading to a 0 or 1 decision and the log of the probability of the path leading to the opposite decision. The log of the probability of the path is represented by a path metric value that is the sum of the state metric and the branch metric at time ‘k’.
The difference between the path metrics is considered only if the best path and its alternate lead to a different decision. In this case, the LLR is computed in the same way as the max-log-map system. By minimizing the path metric difference, one maximizes the probability (path metric) of the path leading to decision 1 versus the path leading to decision 0.
The problem with this approach to the calculation of the LLR within a traditional SOVA is evident when the alternate path leads to the same decision as the best path. In this case, the traditional SOVA does consider the path metric difference in updating the reliability information.
Implementations that generate max-log-map equivalence LLR that do not compromise on performance are needed.